Characteristic
Short description
Order groups is a feature for users to specify strong preferences regarding which orders belong together.
Use
By specifying order groups the user can give the algorithm a hint on how to precombine trips. If needed, the user can also assign vehicles to these order groups.
Examples for scenarios that can be modeled by order groups:
- Area trip planning:
Orders of the same area (e.g. of the same postal code) are preferred to be planned together in one or multiple trips.
- Continuity in periodic planning:
Continuity in the assignments of drivers to customers is preferred to benefit from learning effects of the drivers, customer loyalty etc.
Detailed Consideration
Every Order can be part of (at most) one order group. An order group is characterized by an ID. To link an order to its group, the group ID has to be specified for this order.
Orders with the same group ID are loosely coupled. Specifying such group IDs has no immediate effect on the algorithm's behavior. To make effective use of this feature, the user must activate different options of OrderGroupConsideration.
How to deal with order groups
There are two boolean fields:
- one group per trip: each trip may only contain orders of the same group.
- one trip per group: orders of the same group may not be split among several trips.
Currently, "one trip per group" is only supported in connection with "one group per trip".
If order groups have to be considered, that is, if "one group per trip" is chosen, then orders without a specified order group will remain unplanned.
Example 1 (oneGroupPerTrip and oneTripPerGroup not fulfilled):
In this example there are four orders with group ID A and one order with group ID B. All orders are transport orders with pickup at depot. The tour consists of two trips as the empty vehicle
The term vehicle describes what is being routed or planned for. Vehicles are used in route calculation, distance matrix calculation and effectively also in tour planning. In route calculation, vehicle properties like overall size, weight and speed are in focus. In tour planning, it is vehicle properties like capacity and availability.
Commonly a vehicle is motorized, like a truck - including its trailer or a car. However also a bike or even a pedestrian are included in this definition. has to return to the depot after the third customer. The first trip fulfills the preference oneGroupPerTrip as all orders have the same group ID (A). The second trip does not fulfill the preference, as it contains orders of two different groups (A and B). The preference oneTripPerGroup is not fulfilled either, as both trips have orders of group A.
Example 2 (oneGroupPerTrip and oneTripPerGroup fulfilled):
This example is equal to the first example except that one of the orders of group A is unplanned instead of being served in Trip 2. Thus, both perferences oneGroupPerTrip and oneTripPerGroup are fulfilled.
Plan Tours
Activated options of the OrderGroupConsideration of a PlanToursRequest are considered as restrictions during automatic planning.
Thus, when setting the preferences oneTripPerGroup and oneGroupPerTrip, the algorithm chooses the solution of Example 2 instead of the solution of Example 1, although there are more unplanned orders in Example 2.
However, the OrderGroupConsideration does not lead to violations for tours of an InputPlan.
Thus, when setting the preferences oneTripPerGroup and oneGroupPerTrip, an InputTour like the tour of Example 1 is not considered as violated, i.e. its vehicle will not be referenced in vehicleIdsWithTourViolations.
Fleet Management
To also couple vehicles with order groups, one or multiple orderGroupIds can be specified for Vehicles.
If this list is left empty, it means there are no preferences. If a field of the OrderGroupConsideration is set to true, an order should only be served by a specific vehicle if a) this list is empty or b) this list contains the group ID of the order.
Determination of a Trip's orderGroupId
Each trip has the orderGroupId that occurs most often among all orders of the trip, that is, among those orders with a specified group ID. In case of a tie, the IDs themselves are compared.
Special Case: Input Plan
Suppose there is a trip with three orders given as input. Two of these orders belong to the order group "majority" and the third order belongs to the group "minority". Then the order group ID of the trip is considered to be "majority". In a PlanToursRequest, only orders of group "majority" may be added to this trip. When removing an order from the trip, it is assured that the order group ID of the trip does not change. Still, the whole trip may be dissolved during automatic planning.
If the input trip is served by a non-matching vehicle (that is, the list of order groups is non-empty but does not contain the order group ID of the trip), then no orders are added to the trip.
If the input trip contains orders without a specified order group, then this trip is left untouched.
Change Tours
Actions of ChangeToursRequests are always performed even if options of OrderGroupConsideration are not fulfilled or if any orderGroupId does not match with any of the orderGroupIds of the target vehicle.
ChangeToursActions can change a trip's orderGroupId.
Change Tours Proposals
All possible ChangeToursActions are proposed in a ChangeToursProposalsResponse. Calling a trip 'wrong' for an order if its insertion does not fit to the OrderGroupConsideration and calling a vehicle 'wrong' for an order that does not match with any of the vehicle's orderGroupIds, the proposals are sorted by the following criteria:
- All actions that create a valid tour plan where no order is additionally added to a 'wrong' trip
- All actions that create a valid tour plan where orders are added to 'wrong' vehicles but no order is added to a 'wrong' trip
- All remaining actions
Related Topics
| Showcase | Tour planning with order groups |